\chapter{Basic Concepts}
\label{chapter:BasicConcepts}

This section will be divided into three parts. In Section \ref{section:ProbStat} I will describe the problems in this thesis that I am going to solve. And In Section \ref{section:TheoConcpt} I will describe in detail the theoretical algorithms and concepts that solve the problems stated in Section \ref{section:ProbStat}. Section \ref{section:TechConcpt} introduce the techniques I used this thesis project. Further implementation details will be described in Chapter \ref{chapter:SystemDesign} and Chapter \ref{chapter:SystemImplementation}. 

\section{Problem Statement}
\label{section:ProbStat}


As the title of this thesis reads, the main contribution of our approach is the \emph{streaming} of geometries. Naturally how to achieve streaming becomes the core problem in our approach. \\
%statement of the streaming

For a precise statement of the problems, we have to initially define \emph{mesh streaming} properly. Here is a practical scenario: Suppose there is a mobile device user who would like to view a 3D model remotely stored on a server. In the traditional setup, the 3D model would be transmitted to the client side as a whole package. Once the client side get the whole model it would load it and render it to screen. This solution would be good when the model is small and the transmission of the whole model would be finished in acceptable time. While in the streaming setup, on the user have chosen a model, a rough model simplified from the original model with much smaller size and can be downloaded from client side within an acceptable time. Afterwards, details of the model would be sent to client side and the client side model will be refined on the fly until highest resolution level is reached. During the whole process the 3D model on the client side would be continuously and progressively reconstructed. Based on this scenario, we define \emph{Mesh Streaming} as follows: 
\begin{defn}
\emph{Mesh Streaming} is a process satisfying the following conditions: 
	\begin{enumerate}[label=\roman*]
		\item A rough model of small size is transmitted to the client side in the initial phase.
	  	\item Detail information of the model is transmitted after the initial phase. 
	  	\item Model in the client side can be refined and reconstructed continuously and progressively upon the details received. 
	\end{enumerate}
\end{defn}
%now we have the definition of mesh streaming, we can go further to describe the problem. 
Given the definition of \emph{Mesh Streaming}, we can get the following problems naturally: 
\begin{enumerate}[label=\roman*]
	\item \emph{Mesh representation}\\
	Since our approach is based on 3D models, a polygon mesh representation is initially needed. Therefore we have to find a way to model a 3D mesh with both efficiency and convenience. 
	\item \emph{How to produce small-sized rough models? }\\
	In the initial phase of our approach a small-sized rough mesh has to be generated from the original mesh. How to perform such kind of simplification could be a big topic. In our approach we use the \emph{Quadric Error Metric Method} which we will describe in detail in Section \ref{section:TheoConcpt}. 
	\item \emph{How to reconstruct the original mesh given the rough mesh and details? }\\
	As is stated in the definition of \emph{Mesh Streaming}, the final phase of streaming is reconstruction of the original mesh through the details streamed from the server side. And how to refine the mesh based on detail streamed from the server and finally reconstruct the original mesh becomes another problem we have to solve in this thesis. 
\end{enumerate}

Furthermore, as introduced in Chapter \ref{chapter:introduction}, our approach is providing \emph{view-dependent} streaming. Here we define the term \emph{View-dependent geometry streaming} as follows: 
\begin{defn}
	\emph{View-dependent geometry streaming} is a streaming process, in which the system responds to user's view on the geometry model and stream corresponding detail information for the refinement of the model. 
\end{defn}
This definition raises another question - how to achieve view-dependent streaming? This question is related with a series of problems in data structures and algorithms. \\

In the following chapters of this thesis, we will try to answer and solve the problems raised above. 

\section{Theoretical Concepts}
\label{section:TheoConcpt}
As the problems stated in Section \ref{section:ProbStat}, in this section we will introduce the theoretical concepts which are related to the problems raised. 

\subsection{Notation}
\label{subsection:notation}
In modern computer science, models are usually represented in the form of \emph{triangular meshes}. Here we define a \emph{triangular mesh} as follows:
\begin{defn}
	A \emph{triangular mesh} is a surface consisting of a set of triangles pasted together along their edges\cite{Hoppe:1996:PM}. 
\end{defn}
A triangular mesh $M$ has three kinds of \emph{mesh elements}: vertices, edges and faces. Thus, we have the following definitions:
\begin{defn}
	\emph{Mesh Connectivity}, or topology, is the information of a mesh $M$ which describes incidence relations of mesh elements(\eg, adjacent vertices and edges of a face, \etc).   
\end{defn}
\begin{defn}
	\emph{Mehs Geometry} is the information of a mesh $M$ which specifies the position and other geometric characteristics of each vertex in $M$.
\end{defn}

\input{graphs/GraphDefMesh}

For an edge in mesh $M$ connecting two vertices $v_i$ and $v_j$, we can denote it by $e_{ij}$. And for a single vertex $v_i$, there is a set of 1-ring neighbor vertices that each of them is connected to $v_i$ with an edge. We can denote this vertex set by $N_{v_i}$. (see \FG{fig:DefMesh})

\subsection{Progressive Mesh}
\label{subsection:theoreticalPM}
In the approach proposed in this paper, \emph{progressive mesh} is used as the multi-resolution representation of a mesh. In \cite{Hoppe:1996:PM} Hoppe \etal introduced the concept of \emph{progressive mesh (PM)} based on two basic mesh transformation operations: \textbf{edge collapse} and \textbf{vertex split}. These two transformation operations are essential in the generating and reconstruction phase of a PM respectively. Hence, we will first introduce these two transformations. 

\begin{defn}
	In a triangular mesh $M$, given two vertices $v_u$, $v_t$ and the edge $e_{ut}$ connecting them, an \emph{edge collapse} transformation operation $ecol(v_s,v_u,v_t,v_l,v_r)$ collapses two vertices $v_u$ and $v_t$ connected with edge $e_{ut}$ into a new vertex $v_s$ and produces a new mesh $M'$. Here $v_l$ and $v_r$ are the two vertices in the two triangles sharing edge $e_{ut}$ which remain unchanged during the transformation. 
\end{defn}

The \emph{edge collapse} is defined above. And we can then define \emph{vertex split} as follows:
\begin{defn}
	In a triangular mesh $M$, given a vertex $v_s$ and two new vertex $v_u$ and $v_t$, a \emph{vertex split} transformation operation $vsplit(v_s,v_u,v_t,v_l,v_r)$ splits a vertex $v_s$ into two vertices $v_u$ and $v_t$ and resulting a new mesh $M'$ in which edge $e_{ut}$ connects vertices $v_u$ and $v_t$ and is the sharing edge of the two neighboring triangles: $Triangle(v_u,v_t,v_l)$ and $Triangle(v_u,v_t,v_r)$. 
\end{defn}

\FG{fig:ecol_vsplt_illustration} illustrates the $ecol$ and $vsplit$ transformation operations. Obviously they are reverse operations. The last two parameters of $ecol$ operation are $v_l$ and $v_r$ are the opposite vertices of the edge $e_{ut}$ which is to be collapsed. And in the $vsplit$ operation the last two parameters are also $v_l$ and $v_r$. However, not like those in $ecol$ operation, the $v_l$ and $v_r$ in $vsplit$ operation can be any two different vertices in the neighbor vertices set $N_{v_s} $of $v_s$. These two vertices are crucial in the $vsplit$ operation since they determine the connectivity of $v_u$ and $v_t$ with $N_{v_s}$ after $vsplit$ operation. And as described in \cite{Kim:2003:TransitiveMeshSpace}, we call the vertices $v_l$ and $v_r$ the \emph{cut vertices} of $ecol$ and $vsplit$ operations.  

\input{graphs/GraphEcolVspltillu}

In a general framework of \emph{progressive mesh}, there are two phases, the \emph{simplification phase} and the \emph{reconstruction phase}. In \emph{simplification phase} we perform $ecol$ operation on the original mesh $\hat{M}=M^n$ iteratively until a coarser mesh $M^0$ is produced. On the other hand, in \emph{reconstruction phase} the $vsplit$ operation is iteratively performed on the coarsest mesh $M^0$ which is produced in \emph{simplification phase} until the original mesh $M^n$ is reached. $n$ here indicates the number of reconstruction steps. \\

Therefore we can express the \emph{simplification phase} as follows:
$$
	(\hat{M}=M^n)\xrightarrow{ecol_{n-1}}{M^{n-1}}\xrightarrow{ecol_{n-2}}\ldots\xrightarrow{ecol_1}{M^1}\xrightarrow{ecol_0}{M^0}
$$
In each step in the \emph{simplification phase} from $M^{i+1}$ to $M^i$, we denote an $ecol$ operation of resolution level $i$ by:
$$
	ecol_i=ecol(v_{s_i},v_{t_i},v_{u_i},v_{l_i},v_{r_i}),
$$
where $i\in\{x|x\in{\mathbb{Z}}\wedge 0\le x <n\}$. By performing the $ecol$ operation until the $M^0$ is reached, a sequence of $ecol$ operations is generated: 
$$(ecol_{n-1},ecol_{n-2},\ldots,ecol_{1},ecol_{0})$$
As is stated in the previous paragraph, there is a key observation that the $ecol$ operations are invertible. In other words, in any edge collapse operation $ecol_i$, detail information $d_i$, consisting of $(v_{s_i},v_{t_i},v_{u_i},v_{l_i},v_{r_i})$,is reserved to reconstruct $M^{i+1}$ from $M^{i}$. And if we extract each detail information from the $ecol$ sequence and apply them into $vsplit$ operation in reversed order, we will get a sequence of $vsplit$ operations:
$$
	(vsplit_{0},vsplit_{1},\ldots,vsplit_{n-2},vsplit_{n-1}),
$$
where for any $0\le i < n$, a $vsplit$ can be expressed as:
$$
	vsplit_i=vsplit(v_{s_i},v_{t_i},v_{u_i},v_{l_i},v_{r_i})
$$
Therefore in the \emph{reconstruction phase} an arbitrary triangle mesh $\hat{M}$ can be represented as a simplified mesh $m^0$ together with a sequence of n $vsplit$ records:
$$
	M^0\xrightarrow{vsplit_0}M^1\xrightarrow{vsplit_1}\ldots\xrightarrow{vsplit_{n-2}}M^{n-1}\xrightarrow{vsplit_{n-1}}(M^n=\hat{M})
$$
As described in \cite{Hoppe:1996:PM}, we call $(M^0,\{vsplit_0,\ldots,vsplit_{n-1}\})$ a \emph{progressive mesh} representation of $M$. And the detail information sequence generated from the $ecol$ operations are denoted as \emph{PM sequence}.\\

Note that in a edge collapse operation $ecol_i$, the \emph{cut vertices} $v_{l_i}$ and $v_{r_i}$ are always the opposite vertices of the collapsed edge $e_{{u_i}{t_i}}$. Actually the edge collapse operation $ecol_i$ can be performed without specifying those two cut vertices because the connectivity information among the \emph{cut vertices} $(v_{l_i},v_{r_i})$ and collapsed edge $e_{{u_i}{t_i}}$ is implicitly implied in the \emph{edge collapse} operation itself. However, the cut vertices are still stored as the detail information $d_i$, why? Because when we apply a vertex split operation $vsplit_i$ to $M^i$, the connectivity of the split vertex $v_{s_i}$ and its 1-ring neighbors $N_{v_{s_{i}}}$ in the resulting mesh $M^{i+1}$ is determined by the \emph{cut vertices} of $vsplit_i$, which are originally stored in the detail information $d_i$.  \\

Furthermore, sequential LOD meshes $M^i$ can be naturally generated by using $vsplit_i$ and $ecol_i$ operations. The mesh of LOD lever $i$ can be produced bi-directionally by applying the PM sequence $(vsplit_0,\ldots,vsplit_{i-1})$ or $(ecol_{n-1},\ldots,ecol_{i})$ on the base mesh $M^0$ or on the original mesh $M^n$ respectively. (see \FG{fig:PmExample})
$$
	M^0\underoverrightleftarrow{ecol_{i-1}}{vsplit_{i-1}}\ldots\underoverrightleftarrow{ecol_{i-1}}{vsplit_{i-1}}M^i\underoverrightleftarrow{ecol_i}{vsplit_i}\ldots\underoverrightleftarrow{vsplit_{n-1}}{ecol_{n-1}}M^n
$$

\input{graphs/GraphPMExample}

\subsection{Quadric Error Metrics}
\label{subsection:theoreticalQEM}
%\TODO{theoretical concepts of QEm}
As is described in \SC{subsection:theoreticalPM}, the first step of generating a \emph{progressive mesh} is the \emph{simplification phase}. If we decompose the \emph{simplification phase}, we will get a sequence of \emph{edge collapse} operations. By performing a number of \emph{edge collapse} operations on the original mesh, we will get a coarser mesh with relatively lower resolution. In each single operation of \emph{edge collapse} $ecol_i$, an edge $e_i$ is chosen to be collapsed. Intuitively, edges will be chosen to be collapsed based on the approximating error of applying $ecol$ operation on the chosen one. We will always choose the edge which has the minimal simplification error. Hence, we need an algorithm to produce such $ecol$ sequence. \\

Garland \etal\cite{Garland:1997:SSU} proposed a method using \emph{quadric error metrics (QEM)} for surface simplification. In this thesis we use this method to generate the \emph{edge collapse} sequence. 

\subsubsection{Basic Idea}
\label{QEM:BasicIdea}
Let's first think about a question: how should we evaluate whether a simplification is good or not? Obviously, we evaluate the similarity between the original and simplified mesh. We say a simplification is a good simplification if the simplified mesh \emph{looks like} the original one. \emph{Quadric Error Metrics}\cite{Garland:1997:SSU} provides a way optimally and quickly find a good simplification. \\

For each vertex in a mesh $v_i$ we can express it as the intersection of adjacent faces. We call those faces \emph{$v_i$'s planes} Then we have the following definition:
\begin{defn}
	The \textbf{error at a vertex} $v$ is the sum of the square distances to its planes:
	\begin{equation}
	\Delta(\textbf{v})=\Delta({\begin{bmatrix}v_x & v_y & v_z & 1\end{bmatrix}}^\intercal)=\sum_{\textbf{p}\in{planes(\textbf{v})}} (\textbf{p}^\intercal\textbf{v})^2,
	\label{QEM:ErrV}
	\end{equation}
	where $\textbf{p}={\begin{bmatrix}a & b & c & d\end{bmatrix}}^\intercal$ is the plane $ax+bx+cx+d=0$ with $a^2+b^2+c^2=1.$
\end{defn}

This approximation error metric is initially proposed in \cite{RonfardR:96} and \cite{Garland:1997:SSU}. The set of supporting planes of any vertex $v_i$ is initially determined by the planes of the triangles that intersect at that vertex. We can further derive the error described in \EQ{QEM:ErrV} to a quadric form:


\begin{align}
          \Delta (\textbf{v}) &= \sum_{\textbf{p}\in plane(\textbf{v})}(\textbf{v}^\intercal \textbf{p})(\textbf{p}^\intercal \textbf{v})\\
          \Delta (\textbf{v}) &= \sum_{\textbf{p}\in planes(\textbf{v})}\textbf{v}^\intercal(\textbf{p}\textbf{p}^\intercal)\textbf{v}\\
          \Delta (\textbf{v}) &= \textbf{v}^\intercal\left(\sum_{\textbf{p}\in planes(\textbf{v})}\textbf{K}_{\textbf{p}}\right)\textbf{v}
\end{align}
where $\textbf{K}_{\textbf{p}}$ is the matrix:
$$
	\textbf{K}_{\textbf{p}}=\textbf{pp}^\intercal=
	\begin{bmatrix}
		a^2	&	ab	&	ac	&	ad\\
		ab	&	b^2	&	bc	&	bd\\
		ac	&	bc	&	c^2	&	cd\\
		ad	&	bd	&	cd	&	d^2
	\end{bmatrix}
$$

As is described in \cite{Garland:1997:SSU}, $\textbf{K}_{\textbf{p}}$ is called \emph{fundamental error quadric} with which we can calculate the squared distance of any point in space to the plane $\textbf{p}$. An entire set of supporting planes of a vertex $v$ can be represented by the sum of these fundamental quadrics together: 
\begin{equation}
Q_v=\sum_{i} \textbf{K}_{\textbf{p}_i}
\label{sumofkp}
\end{equation}
As \cite{Garland:1997:SSU} and \cite{RonfardR:96} did, we propagate planes after an edge collapse $ecol(v_u,v_t)\rightarrow\hat{v_s}$ using the approximation rule: $planes(v_s)=planes(v_u)\cup planes(v_t)$. Here we don't have to do a set union computation. Instead we use a approximation of simply adding two quadrics $(\textbf{Q}_u+\textbf{Q}_t)$. Therefore, we can express the error on each edge collapse of vertex $v_u$ and $v_t$ to $v_s$ ($ecol(v_u,v_t)\rightarrow v_s$) as $\textbf{v}_s^\intercal(\textbf{Q}_u+\textbf{Q}_t)\textbf{v}_s$

\input{graphs/GraphEcolIllu}

\subsubsection{Algorithm}
\label{QEM:Algorithm}
Given the basic idea stated in \SC{QEM:BasicIdea}, the algorithm of \emph{Quadric Error Metric} can be summarized as \AL{QEM:algorithmlist}:
\begin{algorithm}                     
\caption{Quadric Error Metrics Algorithm Summary}          
\label{QEM:algorithmlist}                           
\begin{algorithmic}      
 	\FORALL{initial vertices v} 
		\STATE{Compute the $\mat{Q}$ matrix for $v$.} 
	\ENDFOR
	\STATE{Compute and select all valid edges with vertex pairs.}
	 \WHILE{Not done} 
	 	\STATE{For each edge $e(v_u,v_t)$\\
				compute $v_s$ with minimum collapse error 
		} 
		\STATE{Perform $ecol(v_u,v_t)\rightarrow v_s$ with minimal error.}
		\STATE{Setting $\mat{Q}_s=\mat{Q}_u+\mat{Q}_t$ and update candidate edges.}
	\ENDWHILE
\end{algorithmic}
\end{algorithm}

\subsection{View-dependent refinement of Progressive Mesh}
\label{theo:vdpm}
In the scenario of \emph{view-dependent refinement of progressive mesh}, instead of a sequential refinement process of LODs, the base mesh $M^0$ is refined according to user's viewing parameters (angle, perspective \etc). When receive a user viewing parameter, a number of vertices are chosen to be split. And those vertices with fewer viewing contributions remain unchanged or will be performed $ecol$ operation. Therefore in this case, the viewing mesh model are varying dynamically upon user interaction. In this section, we introduce the theoretical backgrounds of \emph{view-dependent refinement of progressive mesh}. 

\subsubsection{Vertex Hierarchy}
\label{subsection:theoreticalVHF}
%\TODO{theoretical concepts of VHF}
In \emph{simplification phase}, a PM sequence is generated with a series of edge collapse operations\cite{Hoppe:1997:VRP}. For each step in the \emph{simplification phase}, an edge collapse operation, $ecol_i=ecol(v_{s_i},v_{t_i},v_{u_i},v_{l_i},v_{r_i})$, implicitly establishes a hierarchical relation between the collapsed vertices $(v_{t_i},v_{u_i})$ and the newly generated vertex $v_{s_i}$. After the whole sequence is generated, a \emph{vertex hierarchy} $H$ is obtained. The vertex hierarchy $H$ is a forest structure and its root nodes are exactly the vertices of the base mesh $M^0$. Similarly leaf nodes of the vertex hierarchy forest $H$ denote corresponding vertices in the original mesh $\hat{M}=M^n$. (See \FG{fig:vhExample})\\
\input{graphs/GraphVhExample}

\subsubsection{Transitive Space of Progressive Meshes}
\label{theo:tspm}
Kim \etal\cite{Kim:2003:TransitiveMeshSpace}\cite{Kim:2001:trulyselective} introduced the concept of \emph{progressive transitive mesh space} of a given mesh $\hat{M}$. The \emph{progressive transitive mesh space $\mat{S}_H(\hat{M})$} has the following characteristics:
\begin{enumerate}
\item
$\mat{S}_H(\hat{M})$ contains all selectively refined meshes that can be obtained from the base mesh $M^0$.
\item
$\mat{S}_H(\hat{M})$ is fixed when the \emph{Vertex Hierarchy} $H$ has been generated from the \emph{simplification phase}. 
\item
Given the same original mesh $\hat{M}$, $\mat{S}_H(\hat{M})$ varies if $\hat{M}$ is simplified in different way. 
\end{enumerate}
With the \emph{transitive progressive mesh space} we can design more effective $ecol$ and $vsplit$ operations and help us to build a view-dependent progressive mesh schema. 
\subsubsection{Dual Perspective of Progressive Mesh}
\label{theo:dppm}
To understand the implicit relation between a mediate mesh in $\mat{S}_H(\hat{M})$ and the finest original mesh $\hat{M}$, we need to first define the \emph{fundamental dual piece} of a vertex $\hat{v}$ in $\hat{M}$ as follows\cite{Kim:2001:trulyselective}: 
\begin{defn}
The \textbf{fundamental dual piece} of $\hat{v}$ $\mathcal{D}_f(\hat{v})$ is the closed region over a given mesh $\hat{M}$, and surrounded by dual edges that connect the dual vertices corresponding to the faces adjacent to $\hat{v}$ (see \FG{fig:fundDualPiece})
\end{defn}
\input{graphs/GraphFundDualPiece}

Moreover, we can define the \emph{dual piece} of a vertex $v$ $\mathcal{D}(v)$ as follows:
\begin{defn}
The \textbf{dual piece} of a vertex $v$ $\mathcal{D}(v)$ in the vertex hierarchy $H$ is the union of fundamental dual pieces of all leaf nodes in the subtree of $H$ whose root is $v$.(See \FG{fig:dualPiece})
\end{defn}
And as Kim \etal\cite{Kim:2001:trulyselective} described, the dual pieces of vertices in a vertex hierarchy $H$ have the following properties:
\begin{enumerate}
\item
$\mathcal{D}(v_{s_i})=\mathcal{D}(v_{t_i})\cup\mathcal{D}(v_{u_i})$ and $\mathcal{D}(v_{t_i})\cap\mathcal{D}(v_{u_i})=\emptyset$, for all $i$.
\item
$\mathcal{D}(v_{t_i})$ and $\mathcal{D}(v_{u_i})$ are adjacent to each other, for all $i$.
\item
$\mathcal{D}(v_q)\subset\mathcal{D}(v_p)$ if $v_p$ is an ancestor of $v_q$ in $H$.
\item
$\mathcal{D}(v_p)\cap\mathcal{D}(v_q)=\emptyset$ if $v_p$ and $v_q$ have no ancestor-descendent relationship in $H$.
\end{enumerate}
\input{graphs/GraphDualPiece}

A common observation is that for the union of the dual pieces of all the vertices in a simplified mesh $M$ cover the original mesh $\hat{M}$ without overlaps and holes. That is to say, the dual pieces from $M$ partition the surface of $\hat{M}$. And with the simplification process goes, the partitioning becomes finer. \\

Now let's go back to this section's topic - \emph{view-dependent progressive mesh}. With the vertex hierarchy and the dual perspective, it is possible to design view-dependent vertex split and vertex collapse operations with responds to user interaction. It is obvious that in the dual space, a $vsplit$ operation is equivalent to re-partitioning a dual piece $\mathcal{D}(v_{s_i})$ into two adjacent dual pieces $\mathcal{D}(v_{u_i})$ and $\mathcal{D}(v_{t_i})$. And the $ecol$ operation is the corresponding inverse transformation of merging two adjacent dual pieces into one. Now the problem is that suppose we wish to split vertex $v_{s_i}$ with $vsplit(v_{s_i}, v_{u_i},v_{t_i},v_{l_i},v_{r_i})$ while the $v_{l_i}$ and $v_{r_i}$ obtained from \emph{simplification phase} are not yet active in the current mesh and cannot be found in current 1-ring neighbors of $v_{s_i}$. Therefore we need to find two vertices in $N(v_{s_i})$, which we call them \emph{cut vertices}, to play the role of $v_{l_i}$ and $v_{r_i}$. \\
\input{graphs/GraphDualPieceSplit}
We can see that the cut vertices of $v_{s_i}$ in its 1-ring neighbors $N(v_{s_i})$ are the vertices whose dual pieces are consecutively adjacent to both $\mathcal{D}(v_{u_i})$ and $\mathcal{D}(v_{t_i})$ and they always exist as is showed in \FG{fig:dualPieceSplit} in the left diagram. Therefore we convert the problem to finding two vertices among $N(v_{s_i})$ whose dual pieces are adjacent to both $\mathcal{D}(v_{u_i})$ and $\mathcal{D}(v_{t_i})$. And in this case, we need to use the hierarchical partitioning property of the dual pieces. Let $\hat{v}_{l_i}$ and $\hat{v}_{r_i}$ are the original cut vertices of $v_{s_i}$ which are currently not active. They are adjacent to both $\mathcal{D}(v_{u_i})$ and $\mathcal{D}(v_{t_i})$. Then, we can obtain that any active ancestor of $\hat{v}_{l_i}$ (or $\hat{v}_{r_i}$), denoted as $v^a_{l_i}$ (or $v^a_{r_i}$) has the same adjacency because $\mathcal{D}(\hat{v}_{l_i})\subset\mathcal{D}(v^a_{l_i})$ (or $\mathcal{D}(\hat{v}_{r_i})\subset\mathcal{D}(v^a_{r_i})$) according to the properties of dual piece. Thus, finding the cut vertices in $N(v_{s_i})$ becomes the problem of finding active ancestor of $\hat{v}_{l_i}$ and $\hat{v}_{r_i}$ among current 1-ring neighbor $N(s_i)$. \\

Therefore, in the scenario of \emph{view-dependent refinement of progressive mesh}, we redefine the $vsplit$ and $ecol$ operations as the follows:
\begin{align}
	vsplit & (v_{s_i},v_{u_i},v_{t_i},\hat{v}_{l_i},\hat{v}_{r_i}) \\
		 & =vsplit(v_{s_i},v_{u_i},v_{t_i},v^a_l,v^a_r)\\
	 ecol&(v_{s_i},v_{u_i},v_{t_i},\hat{v}_{l_i},\hat{v}_{r_i}) \\
	         & =ecol(v_{s_i},v_{u_i},v_{t_i},v^a_l,v^a_r)
\end{align}
where
\begin{align}
	v^a_l & =ActiveAncestor(\hat{v}_{l_i})\\
	v^a_r &=ActiveAncestor(\hat{v}_{r_i})	
\end{align}

This new $ecol$ and $vsplit$ operation definition solves the problem finding \emph{cut vertices}. Therefore in a view-dependent refinement of progressive mesh we can easily traverse in the \emph{transitive mesh space} from any refined mesh $M^i$ to $M^j$ responding to user's viewing parameter. In each LOD, corresponding operations of $ecol$ or $vsplit$ will be performed according viewing contribution of affecting vertices. 


\section{Technical Concepts}
\label{section:TechConcpt}
%\TODO{In this section, we will introduce the techniques we used in this project. }
Since the major contribution of our thesis is in the perspective of application implementation, in this section we will introduce some technical concepts which are important to the implementation of our geometry streaming framework. In \SC{section:implQEM} the implementation detail of \emph{quadric error metric} method will be described. \SC{section:implVH} will introduce the efficient implementation of the \emph{vertex hierarchy forest} which contributes to the implementation of \emph{view-dependent refinement of progressive mesh}. Then \SC{section:openmesh} introduces the an open-source mesh representation framework \emph{OpenMesh} we use in this thesis. At last, the programming tools and technologies we used to implementation our system will be described in \SC{section:progTools}.

\subsection{Implementation of QEM}
\label{section:implQEM}
As illustrated in \AL{QEM:algorithmlist}, it needs to trace every edge in the whole mesh and in each in each iteration searches for the edge with vertices which have minimum quadric error, remove it from the mesh and then update the costs of all valid edges involved. Therefore we need an efficient data structure to store edges' error information and a fast algorithm to retrieve the edge with minimum error. Naturally we choose to use the \emph{minimum heap} to store all the edge error information. Thus, we can build the heap in $O(n)$ time and each removal of a minimum cost edge costs $O(\log{n})$

\subsection{Efficient Implementation of Vertex Hierarchy}
\label{section:implVH}
As is described in \SC{theo:tspm} the key point view-dependent refinement is that, for each $ecol$ or $vsplit$ operation, we need to find its cut vertices $v_l$ and $v_r$. And the way to find cut vertices is to find active ancestors ($v^a_l$ and $v^a_r$) of its \emph{fundamental cut vertices} among the current 1-ring neighbor $N(v_s)$. 

\input{graphs/GraphVhEncoding}

For the view-dependent $ecol$ operation, find the \emph{cut vertices} is quite straight forward. (see \FG{fig:ecol_vsplt_illustration}) However to find the \emph{cut vertices} in a view-dependent $vsplit$ operation we have to use the \emph{vertex hierarchy structure} to find the active ancestors. We are inspired by \cite{Kim:2001:trulyselective} and use the bit-wise approach to represent the vertex hierarchy structure. To speed up the $vsplit$ operation, each node in the vertex hierarchy $H$ is encoded as $<treeId,nodeId>$ notation. Naturally nodes in the same tree in $H$ share the same $treeId$. And for any node $<treeId_n,nodeId_i>$ in a tree, its two children's $nodeId$ are encoded as $<treeId_n,2\cdot nodeId_i>$ and $<treeId_n,2\cdot nodeId_i+1>$. The $nodeId$ of root node is always $1$. (see \FG{fig:vhEncoding}) Based on this encoding schema, an $IsAncestor(v^a,v_d)$ procedure can be designed to test if $v^a$ is the ancestor of $v_d$ via simply check their $<treeId,nodeId>$ notation. Vertex $v^a$ is the ancestor of $v_d$ \textbf{if and only if} the following two conditions both hold:
\begin{enumerate}
\item
$treeId_{v^a}=treeId_{v_d}$
\item
Define function $f(x)=\lfloor\frac{x}{2}\rfloor$ and $f^{n+1}=f^n(f(x))$, $f^{1}(x)=f(x)$ , $\exists{n}\in\mathbb{N}$ and $0<n\le\lceil\log{(nodeId_{v_d})}\rceil:{nodeId_{v^a}}=f^n(nodeId_{v_d})$.
\end{enumerate}

With the fact that each tree in the vertex hierarchy forest is actually a binary tree, we can represent each $nodeId$ with a 64-bit unsigned integer and the procedure of $IsAncestor$ can be simply implemented with binary shift operation within $O(1)$ time. Therefore we can locate the cut vertices $v^a_l$ and $v^a_r$ by testing each vertex in the 1-ring neighbor set of the split vertex $v_s$ with the $IsAncestor$ procedure given $v_s$'s fundamental cut vertices $\hat{v}_l$ and $\hat{v}_r$. This process can be finished within $O(m)$ time, where $m$ is the number of vertices in the current 1-ring neighbor $N(v_s)$. 

\subsection{Mesh Data Structure}
\label{section:meshdatastruct}
%introduce opemmesh framework
In our application, there is a heavy use of geometry mesh structure. And meanwhile, during the transformation operation $ecol$ and $vsplit$ in the progressive mesh, the 1-ring neighborhood of a specific vertex is essential for find the \emph{cut vertices}. Therefore, an efficient, easy-to-use data structure to represent the geometry mesh is highly needed. We choose \emph{OpenMesh}\cite{Botsch02openmesh}, an open-source data structure framework for polygonal meshes, in this project for mesh representation and manipulation.

\subsubsection{OpenMesh}
\label{section:openmesh}
OpenMesh is a generic and efficient data structure and library implemented in C++, for representing and manipulating polygonal meshes. OpenMesh was designed with the following goals: 
\begin{enumerate}
\item
Flexibility : provide a basis for many different algorithms without the need for adaptation.
\item
Efficiency : maximize time efficiency while keeping memory usage as low as possible.
\item
Ease of use : wrap complex internal structure in an easy-to-use interface.
\end{enumerate}
To accomplish these goals following features are provided in OpenMesh:
\begin{enumerate}
\item
Representation of arbitrary polygonal (the general case) and pure triangle meshes (providing more efficient, specialized algorithms)
\item
Explicit representation of vertices, halfedges, edges and faces.
\item
Fast neighborhood access, especially the one-ring neighborhood (see below).
\item
Highly customizable :
\subitem 
Choose your coordinate type (dimension and scalar type)
\subitem
Attach user-defined elements/functions to the mesh elements.
\subitem
Attach and check for attributes.
\subitem
Attach data at runtime using dynamic properties.
\end{enumerate} 

\subsubsection{Half-edge Data Structure}
\label{section:heDataStruct}
Normally, polygonal meshes are consisted of two key elements: geometry (vertices) and topology (edges, faces). And the data structure for polygonal meshes can be categorized in the different ways they store the topology information. In face-based structures the connectivity in faces referencing their vertices and neighbors is stored while the explicit representation of edges is missing. And in edge-based structures the connectivity information is stored into edges with but low efficiency because of their missing orientation of edges.  \\

If one now splits the edges (\ie an edge connecting vertex A and vertex B becomes two directed half-edges from A to B and vice versa) one gets a half-edge-based data structure. In a half-edge data structure as is showed in \FG{fig:halfedge}, each edge connecting two vertices is broken into two opposite directed edges, each pointing to the two ends of the original edge. Hence, (1) for each vertex it will have an outgoing half-edge with corresponding edge connected, (2) each face is bounded with a ring of half-edges with same direction, (3) each half-edge has a target vertex, (4) each half-edge has its corresponding bounded face, (5) give a half-edge we can find its next half-edge, (6) each half-edge has implicitly an opposite half-edge and (7) optionally we can store the previous half-edge information in each half-edge. 
\input{graphs/GraphHalfEdge}

Intuitively, this provides a natural and simple way to represent vertices, edges and faces, as well as arbitrary polygons. As is already stated in previous sections, in our progressive algorithms the \emph{1-ring neighbors} of a vertex is frequently used. Via the half-edge data structure locating the 1-ring neighbors of a given vertex can be done very efficiently. As is illustrated in \FG{fig:onering}, repeating step (2) to (4) will result in the 1-ring neighbors of a given vertex as showed. 
\input{graphs/GraphOneRing}

\subsection{Programming Language and Tools}
\label{section:progTools}

In the implementation of this thesis project, several programming languages, techniques and tools are used. \\

The server side is purely implemented in C++. We integrated the OpenMesh framework in the server side application. The server side is programmed in \textbf{Xcode\footnote{\label{XCODE}\url{https://developer.apple.com/xcode/}} } in C++ on Mac OSX operating system. It is also possible to compile on Windows systems within Visual Studio. We use  \textbf{Poco\footnote{\label{POCO}\url{http://pocoproject.org}} } library to establish the socket server for network transmission. For server rendering we used the OpenGL. 

The client side's code is a mixture of C/C++ and Objective-C. We managed to integrate and compile the OpenMesh framework on the \emph{iOS} system. The client side is mainly programmed in Objective-C, with some C/C++ code inserted into some Objective-C functions in \textbf{Xcode} on Mac OSX operating system. And for the rendering part OpenGL ES is used. 

And we also used \textbf{OpenGL Shading Language} for the shader used in both part. 

%Picture
%\noindent
%\begin{minipage}{\linewidth}
%\makebox[\linewidth]{%
%\includegraphics[width=1.0\textwidth]{images/morphable.pdf}}
%\captionof{figure}{MorphableUI generates user-tailored interfaces for arbitrary applications in arbitrary environments. Users are able to use all available devices to control as many applications as needed. User behavior is analyzed by the system to increase the user experience.}% only if needed
%\label{fig:morphable}
%\bigskip
%\end{minipage}


